package offerv1;

public class Offer26 {
    public boolean isSubStructure1(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }

        if (A != null && B != null) {
            boolean ret1 = isSubStructure(A.left, B);
            boolean ret2 = isSubStructure(A.right, B);

            if (A.val == B.val) {
                return ret1 || ret2 || isSubStructure(A.left, B.left) && isSubStructure(A.right, B.right);
            } else {
                return ret1 || ret2;
            }
        }

        return false;
    }

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}
